package m202405.d16;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/16 16:23
 */
public class Q279 {

    public static void main(String[] args) {
        Q279 q279 = new Q279();
        q279.numSquares(12);
    }

    //n = 11
    //f(11) = 1 + min(f(11-9),f(11-4),f(11-1))
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = findMin(dp, i) + 1;
        }
        return dp[n];
    }

    private int findMin(int[] dp, int n) {
        int min = Integer.MAX_VALUE;
        double sqrt = Math.sqrt(n);
        for (int i = 1; i <= sqrt; i++) {
            min = Math.min(dp[n - i * i], min);
        }
        return min;
    }


}
